A. Nastya and Rice
题目大意：有个石头，每个石头的重量在之间，问所有石头的重量总和有没有可能在之间，输出正确与否即可。
数据范围：范围内
解法：直接判断最大值和最小值有没有可能在区间内即可。
B. Nastya and Door
题目大意：定义山峰是一个区间里除了首尾两个端点之外的，满足值大于左右两边的值的位置。给定区间长度，求出以开始的长度为的区间里最多包含几个山峰的数量，并加一作为答案，以及起始的坐标。如果有相同的则取最左端的。
数据范围：范围内
解法：前缀和求区间内有多少个满足条件的，特别判断一下端点有没有被计入答案，如果有则挖掉即可。
C. Nastya and Strange Generator
题目大意：给你一个排列数生成器，他按如下的规则产生一个排列：
①当前在第步时，放的数就是。
②对每个计算出，表示以及之后最近的空位的下标是多少，如果没有则不记。
③在所有的里选出合法且数量最多的，放入这个位置。
现给定一个排列，问这个排列是否有可能是这个生成器产生的，只需要输出正确性。
数据范围：
解法：生成所有合法序列显然不可行，考虑每个点是不是合法的。
首先，数字是按顺序放入序列的，那么整个序列的正确性应该是与放的顺序相关的，故应该从这里入手。
假设是放在位置上的，放进去之后会使得下一步的序列里，上的变成，这意味着只能放在这个位置上，除非后面没位置了。因此可以推出这个题的结论就是：整个序列如果有上升的部分，那么他一定是连续上升的，否则不正确。最后遍历做个判断就可以了。
代码：
const int N = 1e5+7;
int a[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
int ok = 1;
for(int i = 1;i <= n - 1;++i)
{
if(a[i] < a[i + 1] && a[i] + 1 != a[i + 1])
{
ok = 0;
break;
}
}
if(!ok) puts("No");
else puts("Yes");
}
return 0;
}
D. Nastya and Scoreboard
题目大意：有个灯，每个灯是有个灯管工作显示数字的，但是现在灯管被砸坏了个，问：恰好点亮个灯管之后，能得到的最大数字是多少。要求数字合法，且允许前导0存在。
数据范围：
解法：一个很直接的想法就是。
设状态表示前个里开上了个灯管之后，能获得的最大的数字是多少，然而这个做法很快就可以被推翻掉，因为时间复杂度上过不去，枚举和的复杂度还要带上一个比较字符串大小的，这说明这个思路就有问题。但是不代表不行，实际上可以退而求其次，只保留可行性，而不直接求出具体方案。在求的了当前这个状态的可行性之后，直接把方案构造出来就可以了。
状态：表示当前已经修完了号和之前的所有灯，已经用掉了个灯管，当前这个状态是否是可以合法的。
入口：
出口：代表有解，否则无解
转移：
但是这样还是不够，因为没有考虑到：恰好用完所有次开灯的机会这个条件。可以发现如果正着去考虑的话，整个方案到最后是不是合法的？不知道，因为之后构造方案的时候根本没办法在最后一步说能恰好把次机会用完。换个角度：入口是一个实际的点，他不应该是这个所有都没开的状态，而应该是这个状态，如果初始只有这个点是合法的，那么以他作为入口推得的所有状态显然最后一定会到达这个表示恰好用完了所有灯管的状态，才是正确的。同时，出口也要变换一下，这个时候才是出口，如果这个状态不合法的话就说明没有合法方案，输出无解。
第一问就是一个可行性的。
第二问是求出一个具体方案来，就比较好想了。直接从前往后遍历，优先满足前面最大的能得到的值。由于所有可行性的状态都是由转移而来的，故最后一定会把推到，输出方案即可。
代码：
typedef long long ll;
const int N = 2005;
int f[N][N];
const string table[13] = {"1110111","0010010","1011101","1011011","0111010","1101011","1101111","1010010","1111111","1111011"};
int gdist(const string& a,const string& b)
{
int res = 0;
for(int i = 0;i < 7;++i)
{
if(a[i] == '1' && b[i] == '0') return -1;
if(a[i] == '0' && b[i] == '1') ++res;
}
return res;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int n,m;cin >> n >> m;
vector<string> a(n + 17);
for(int i = 1;i <= n;++i) cin >> a[i];
f[n + 1][0] = 1;
for(int i = n;i >= 1;--i)
for(int k = 0;k <= 9;++k)
{
int w = gdist(a[i],table[k]);
if(w == -1) continue;
for(int j = w;j <= m;++j)
f[i][j] |= f[i + 1][j - w];
}
if(!f[1][m])
{
cout << -1;
return 0;
}
string res;
for(int i = 1;i <= n;++i)
{
for(int k = 9;k >= 0;--k)
{
int w = gdist(a[i],table[k]);
// if(i == 1) cout << w << endl;
if(w != -1 && m >= w && f[i + 1][m - w])
{
m -= w;
res += char(k + '0');
break;
}
}
}
cout << res << endl;
return 0;
}